/*
 * @lc app=leetcode.cn id=70 lang=javascript
 *
 * [70] 爬楼梯
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */

var climbStairs = function(n, progressMap = new Map()/* 存储中间过程Map表防止每次都重复计算后超出时间（时间复杂度过大） */) {
    // 初始化result
    let result = 0
    // 递归结束条件
    // 一级台阶和二级台阶时只有可能是一种情况和两种情况
    if(n === 1) return 1
    if(n === 2) return 2
    // 首先检查Map表中是否已经存在该n的计算结果
    if(progressMap.has(n)) {
        // 存在则直接返回
        return progressMap.get(n)
    }
    else {
        // 不存在则计算并存储
        // 通过动态规划计算
        // 转移方程为f(n)=f(n-1)+f(n-2)，即n阶台阶的爬法数量等于n-1阶台阶的爬法数量加上n-2阶台阶的爬法数量
        // 这个问题类似于斐波那契数列问题
        // 假设n为3，则n-1为2，n-2为1
        result = climbStairs(n-1, progressMap) + climbStairs(n-2, progressMap)
        // 存储计算结果
        progressMap.set(n, result)
        return result
    }
};
// @lc code=end

